Abstract
I introduce TrieHash an algorithm for constructing perfect hash functions from tries. The generated hash functions are pure C code, minimal, order-preserving and outperform existing alternatives. Together with the generated header files,they can also be used as a generic string to enumeration mapper (enums are created by the tool).
Introduction
APT (and dpkg) spend a lot of time in parsing various files, especially Packages files. APT currently uses a function called AlphaHash which hashes the last 8 bytes of a word in a case-insensitive manner to hash fields in those files (dpkg just compares strings in an array of structs).
There is one obvious drawback to using a normal hash function: When we want to access the data in the hash table, we have to hash the key again, causing us to hash every accessed key at least twice. It turned out that this affects something like 5 to 10% of the cache generation performance.
Enter perfect hash functions: A perfect hash function matches a set of words to constant values without collisions. You can thus just use the index to index into your hash table directly, and do not have to hash again (if you generate the function at compile time and store key constants) or handle collision resolution.
As #debian-apt people know, I happened to play a bit around with tries this week before guillem suggested perfect hashing. Let me tell you one thing: My trie implementation was very naive, that did not really improve things a lot
Enter TrieHash
Now, how is this related to hashing? The answer is simple: I wrote a perfect hash function generator that is based on tries. You give it a list of words, it puts them in a trie, and generates C code out of it, using recursive switch statements (see code generation below). The function achieves competitive performance with other hash functions, it even usually outperforms them.
Given a dictionary, it generates an enumeration (a C
enum or C++
enum class) of all words in the dictionary, with the values corresponding to the order in the dictionary (the order-preserving property), and a function mapping strings to members of that enumeration.
By default, the first word is considered to be 0 and each word increases a counter by one (that is, it generates a minimal hash function). You can tweak that however:
= 0
WordLabel ~ Word
OtherWord = 9
will return 0 for an unknown value, map Word to the enum member
WordLabel and map OtherWord to 9. That is, the input list functions like the body of a C enumeration. If no label is specified for a word, it will be generated from the word. For more details see the documentation
C code generation
switch(string[0] 32)
case 't':
switch(string[1] 32)
case 'a':
switch(string[2] 32)
case 'g':
return Tag;
return Unknown;
Yes, really recursive switches they directly represent the trie. Now, we did not really do a straightforward translation, there are some optimisations to make the whole thing faster and easier to look at:
First of all, the
32 you see is used to make the check case insensitive in case all cases of the switch body are alphabetical characters. If there are non-alphabetical characters, it will generate two cases per character, one upper case and one lowercase (with one break in it). I did not know that lowercase and uppercase characters differed by only one bit before, thanks to the clang compiler for pointing that out in its generated assembler code!
Secondly, we only insert breaks only between cases. Initially, each case ended with a return Unknown, but guillem (the dpkg developer) suggested it might be faster to let them fallthrough where possible. Turns out it was not faster on a good compiler, but it s still more readable anywhere.
Finally, we build one trie per word length, and switch by the word length first. Like the 32 trick, his gives a huge improvement in performance.
Digging into the assembler code
The whole code translates to roughly 4 instructions per byte:
- A memory load,
- an or with 32
- a comparison, and
- a conditional jump.
(On x86, the case sensitive version actually only has a cmp-with-memory and a conditional jump).
Due to
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77729 this may be one instruction more: On some architectures an unneeded zero-extend-byte instruction is inserted this causes a 20% performance loss.
Performance evaluation
I run the hash against all 82 words understood by APT in Packages and Sources files, 1,000,000 times for each word, and summed up the average run-time:
| host |
arch |
Trie |
TrieCase |
GPerfCase |
GPerf |
DJB |
| plummer |
ppc64el |
540 |
601 |
1914 |
2000 |
1345 |
| eller |
mipsel |
4728 |
5255 |
12018 |
7837 |
4087 |
| asachi |
arm64 |
1000 |
1603 |
4333 |
2401 |
1625 |
| asachi |
armhf |
1230 |
1350 |
5593 |
5002 |
1784 |
| barriere |
amd64 |
689 |
950 |
3218 |
1982 |
1776 |
| x230 |
amd64 |
465 |
504 |
1200 |
837 |
693 |
Suffice to say, GPerf does not really come close.
All hosts except the x230 are Debian porterboxes. The x230 is my laptop with a a Core i5-3320M, barriere has an Opteron 23xx. I included the DJB hash function for another reference.
Source code
The generator is written in Perl, licensed under the MIT license and available from
https://github.com/julian-klode/triehash I initially prototyped it in Python, but guillem complained that this would add new build dependencies to dpkg, so I rewrote it in Perl.
Benchmark is available from
https://github.com/julian-klode/hashbench
Usage
See the script for POD documentation.
Filed under:
General 
My monthly report covers a large part of what I have been doing in the free software world. I write it for 
What happened in the 
Some impressions from the TorDevMeeting and the Internet Freedom Festival (IFF) in Valencia
Overheard at the Tor Dev meeting in Valencia, from people speaking about online identities: "You were on top of the list of the people I thought were you."
It was really good to be there as my plan to meet people and work on torbrowser-launcher issues worked out nicely: in total seven bugs got fixed upstream and resulted in an torbrowser-launcher upload to sid after the meeting. So now only three bugs are open in sid and it's clear how to fix #811499 in stable so that torbrowser-launcher doesn't stop working on May 3rd 2016. So yay.
At the IFF we also had a small reproducible builds Debian meeting, where I took these raw notes: (please ask for clarifications, how to help or correct me if you think other things are blockers right now as well!)
I just released sbuild 0.66.0-1 into unstable. It fixes a whopping 30 bugs!
Thus, I'd like to use this platform to:
This was my sixth month working on Debian LTS. I was assigned 10.5
hours
by 
